package cn.zifangsky.stack;

import java.util.EmptyStackException;

/**
 * 使用重复倍增数据实现栈结构
 * @author zifangsky
 */
public class ArrayStack implements Stack<Integer>{
	private int top; //栈顶元素位置
	private int capacity; //栈的容量
	private int[] array; //存储栈的数组
	
	public ArrayStack() {
		capacity = 1;
		top = -1;
		array = new int[capacity];
	}
	
	/**
	 * 返回栈是否是空栈
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
    public boolean isEmpty(){
		return (top == -1);
	}
	
	/**
	 * 返回是否是满栈
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public boolean isFull(){
		return (top == capacity -1);
	}

	@Override
	public boolean contains(Integer data) {
		if(data != null){
            for(int temp : array){
                if(temp == data){
                    return true;
                }
            }
        }

		return false;
	}

	/**
	 * 入栈
	 * @时间复杂度 O(1)
	 * @param data 入栈数据
	 */
	@Override
	public void push(Integer data){
		if(isFull()){
			doubleStack();
		}
		array[top+1] = data;
		top++;
	}
	
	/**
	 * 出栈：移动栈顶指针并返回数据
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public Integer pop(){
		if(isEmpty()){
			throw new EmptyStackException();
		}else{
			int result = array[top];
			top--;
			return result;
		}
	}
	
	/**
	 * 返回最后一个插入栈的元素，但不删除
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public Integer top(){
		if(isEmpty()){
			throw new EmptyStackException();
		}else{
			return array[top];
		}
	}
	
	/**
	 * 返回存储在栈中的元素个数
	 * @时间复杂度 O(1)
	 * @return
	 */
	@Override
	public int size(){
		return top+1;
	}
	
	/**
	 * 删除整个栈
	 * @时间复杂度 O(1)
	 */
	@Override
	public void deleteStack(){
		top = -1;
	}
	
	/**
	 * 将栈的容量扩大两倍
	 */
	private void doubleStack(){
		int[] newArray = new int[capacity * 2];
		System.arraycopy(array, 0, newArray, 0, capacity);
		capacity = capacity * 2;
		array = newArray;
	}

	/**
	 * 遍历整个栈
	 * @时间复杂度 O(n)
	 * @return
	 */
	@Override
	public void print() {
		if(array != null && array.length > 0){
			for(int data : array){
				System.out.print(data + " ");
			}
		}
		
	}

}
